#coding=utf-8
#全排列
def permutations(arr:list) -> list:
  # 递归出口
  lenarr = len(arr)
  if lenarr <= 1:
      return [arr]
  else:
      res = []
      for i in range(lenarr):
          temp = arr[:i] + arr[i+1:]
          for j in permutations(temp):
              res.append([arr[i]]+j)
      return res

# arr = [1, 2, 3]
# print(permutations(arr))


# #汉诺塔
def hanoi(n,source,target,helper):
  if n==1:
    moveSingleDesk(source,target)
  else:
    hanoi(n-1,source,helper,target)
    moveSingleDesk(source,target)
    hanoi(n-1,helper,target,source)
def moveSingleDesk(source,target):
  disk = source[0].pop()
  print("moving " + str(disk) + " from " + source[1] + " to " + target[1])
  target[0].append(disk)

# A = ([4,3,2,1] , "A")
# B = ([] , "B")
# C = ([] , "C")
# hanoi(len(A[0]),A,B,C)


#
#最长同值路径
class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right


def find_maxroad(tree_root):
  global maxnum
  if not tree_root:
    return 0  # 出口
  else:
    left_max_num, right_max_num = find_maxroad(tree_root.left), find_maxroad(tree_root.right)
    if tree_root.left and tree_root.val == tree_root.left.val:
      left = left_max_num + 1
    else:
      left = 0
    if tree_root.right and tree_root.val == tree_root.right.val:
      right = right_max_num + 1
    else:
      right = 0
    maxnum = max(maxnum, left + right)
  return max(left, right)

#
# tree = TreeNode(5, TreeNode(4, TreeNode(1), TreeNode(1)), TreeNode(5, right=TreeNode(5)))
# maxnum = 0
# find_maxroad(tree)
# print(maxnum)